package day02

// day02
//
// 121. 买卖股票的最佳时机
//
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
//
// ```go
func maxProfit(prices []int) int {
	//dp[i][0]:第i填不持股 dp[i][1]:第i填持股
	dp := make([][2]int, len(prices))
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	//dp[i][0]=max(dp[i-1][0], dp[i-1][1]+price[i])
	//dp[i][1]=max(dp[i-1][0]-price[i], dp[i-1][1])
	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
		dp[i][1] = max(dp[i-1][1], -prices[i])
	}
	return dp[len(prices)-1][0]
}

//```

// 122. 买卖股票的最佳时机 II
//
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
//
// ```go
func maxProfit(prices []int) int {
	//dp[i][0]:第i填不持股 dp[i][1]:第i填持股
	dp := make([][2]int, len(prices))
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	//dp[i][0]=max(dp[i-1][0], dp[i-1][1]+price[i])
	//dp[i][1]=max(dp[i-1][0]-price[i], dp[i-1][1])
	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
	}
	return dp[len(prices)-1][0]
}

//```

// 123. 买卖股票的最佳时机 III
//
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
//
// ```go
func maxProfit(prices []int) int {
	//dp[i][j],第i天买,状态j下所剩最大金额,j:0-4
	//0:无操作
	//1:第1次买->dp[i][1], 第i天买 or 沿用第i-1天
	// dp[i][1]=max(dp[i-1][0]-prices[i], dp[i-1][1])
	//2:第1次卖->dp[i-1][1], 第i天卖 or 沿用第i-1天
	// dp[i][2]=max(dp[i-1][1]+prices[i], dp[i-1][2])
	//3:第2次买->dp[i][3], 第i天买 or 沿用第i-1天
	// dp[i][3]=max(dp[i-1][2]+prices[i], dp[i-1][3])
	//4:第2次卖->dp[i][4], 第i天卖 or 沿用第i-1天
	// dp[i][4]=max(dp[i-1][3]+prices[i], dp[i-1][4])
	dp := make([][5]int, len(prices))
	dp[0][1] = -prices[0]
	dp[0][2] = 0
	dp[0][3] = -prices[0]
	dp[0][4] = 0
	for i := 1; i < len(prices); i++ {
		dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
		dp[i][2] = max(dp[i-1][1]+prices[i], dp[i-1][2])
		dp[i][3] = max(dp[i-1][2]-prices[i], dp[i-1][3])
		dp[i][4] = max(dp[i-1][3]+prices[i], dp[i-1][4])
	}
	return dp[len(prices)-1][4]
}

//```

// 188. 买卖股票的最佳时机 IV
//
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
//
// ```go
func maxProfit(k int, prices []int) int {
	if k == 0 {
		return 0
	}
	dp := make([][]int, len(prices))
	for i := range dp {
		dp[i] = make([]int, 2*k+1)
	}
	for j := 0; j < 2*k; j++ {
		if j%2 == 0 {
			dp[0][j] = 0
		} else {
			dp[0][j] = -prices[0]
		}
	}
	for i := 1; i < len(prices); i++ {
		for j := 1; j <= 2*k; j++ {
			if j%2 == 0 {
				dp[i][j] = max(dp[i-1][j-1]+prices[i], dp[i-1][j])
			} else {
				dp[i][j] = max(dp[i-1][j-1]-prices[i], dp[i-1][j])
			}
		}
	}
	return dp[len(prices)-1][2*k]
}

//```
